
#include "reverse_iterator.h"

namespace my_list
{

    template<class T>
    struct __list_node
    {
        T _data;
        __list_node* _prev;
        __list_node* _next;

        __list_node(const T& x = T())
            :_data(x)
             ,_prev(nullptr)
             ,_next(nullptr)
        {}

    };

    template<class T, class Ref, class Ptr>
    struct __list_iterator
    {
        typedef __list_iterator<T, Ref, Ptr> iterator;
        typedef __list_node<T> Node;

        __list_iterator(Node* node)
            :_node(node)
        {}
        
        bool operator==(const iterator& it) const { return _node == it._node; }
        bool operator!=(const iterator& it) const { return _node != it._node; }

        Ref operator*() const { return _node->_data; }
        Ptr operator->() const { return &(operator*()); }

        iterator& operator++()
        {
            _node = _node->_next;

            return *this;
        }
        iterator operator++(int)
        {
            iterator tmp(*this);
            _node = _node->_next;
            return tmp;
        }

        iterator& operator--()
        {
            _node = _node->_prev;
            return *this;
        }
        iterator operator--(int)
        {
            iterator tmp(*this);
            _node = _node->_prev;

            return tmp;
        }

        iterator operator+(size_t n)
        {
            iterator tmp(*this);

            while (n -- )
            {
                ++ tmp;
            }

            return tmp;
        }
        iterator operator-(size_t n)
        {
            iterator tmp(*this);

            while (n -- )
            {
                -- tmp;
            }

            return tmp;
        }

        Node* GetNode() { return _node; }

    private:

        Node* _node;

    };

    template<class T>
    class list 
    {
        typedef __list_node<T> Node;

    public:

        typedef __list_iterator<T, T&, T*> iterator;
        typedef __list_iterator<T, const T&, const T*> const_iterator;
        typedef my_riterator::__reverse_iterator<iterator, T&, T*> riterator;
        typedef my_riterator::__reverse_iterator<const_iterator, const T&, const T*> const_riterator;

        iterator begin() { return iterator(_head->_next); }
        const_iterator begin() const { return const_iterator(_head->_next); }
        iterator end() { return iterator(_head); }
        const_iterator end() const { return const_iterator(_head); }

        riterator rbegin() { return riterator(end()); }
        riterator rend() { return riterator(begin()); }
        const_riterator rbegin() const { return const_riterator(end()); }
        const_riterator rend() const { return const_riterator(begin()); }

        void Init_head()
        {
            _head = new Node;
            _head->_next = _head;
            _head->_prev = _head;
        }

        list() { Init_head(); }

        template<class InputIterator>
        list(InputIterator first, InputIterator last)
        {
            Init_head();
            while (first != last)
            {
                push_back(*first);
                ++ first;
            }
        }

        list(size_t n, const T& x = T())
        {
            Init_head();

            for (size_t i = 0; i < n; i ++ )
            {
                push_back(x);
            }
        }
        list(int n, const T& x = T())
        {
            Init_head();

            for (int i = 0; i < n; i ++ )
            {
                push_back(x);
            }
        }

        list(const list<T>& l)
        {
            Init_head();
            list<T> tmp(l.begin(), l.end());
            swap(_head, tmp._head);
        }

        void push_back(const T& x)
        {
            //Node* newnode = new Node(x);
            //Node* prev = _head->_prev;
            //prev->_next = newnode;
            //newnode->_prev = prev;
            //newnode->_next = _head;
            //_head->_prev = newnode;
            
            insert(end(), x);
        }

        void push_front(const T& x)
        {
            insert(begin(), x);
        }

        void pop_back()
        {
            erase(-- end());
        }

        void pop_front()
        {
            erase(begin());
        }

        iterator insert(iterator pos, const T& x)
        {
            Node* newnode = new Node(x);
            Node* cur = pos.GetNode();
            Node* prev = cur->_prev;
            prev->_next = newnode;
            newnode->_prev = prev;
            newnode->_next = cur;
            cur->_prev = newnode;

            return iterator(newnode);
        }

        iterator erase(iterator pos)
        {
            Node* cur = pos.GetNode();
            Node* prev = cur->_prev;
            Node* next = cur->_next;

            delete cur;

            prev->_next = next;
            next->_prev = prev;

            return iterator(next);
        }

        bool empty() const { return begin() == end(); }

    private:
        Node* _head;
    };

}
